package com.lw.leetcode.linked.b;


import com.lw.leetcode.linked.Node;

/**
 * 剑指 Offer II 029. 排序的循环链表
 *
 * @Author liw
 * @Date 2021/8/29 22:14
 * @Version 1.0
 */
public class Insert {
    public Node insert(Node head, int insertVal) {
        Node n = new Node(insertVal);
        if (head == null) {
            n.next = n;
            return n;
        }
        Node root = head;
        while (true) {
            Node next = head.next;
            if (head.val > next.val) {
                if (head.val <= insertVal || next.val >= insertVal) {
                    head.next = n;
                    n.next = next;
                    break;
                }
            } else {
                if (head.val <= insertVal && next.val >= insertVal) {
                    head.next = n;
                    n.next = next;
                    break;
                }
            }
            if (next == root) {
                head.next = n;
                n.next = next;
                break;
            }
            head = next;
        }
        return root;
    }
}

